package 算法.leetcode.labuladong.数组和链表;

import 算法.leetcode.offer.base.ListNode;

/**
 * @author lchenglong
 * @date 2022/6/16
 */
public class 反转链表II {
    class Solution {
        ListNode successor = null;
        public ListNode reverseBetween(ListNode head, int left, int right) {
            if (left == 1){
                return reverseN(head,right);
            }
            // 前进到反转的起点触发 退出条件
            head.next = reverseBetween(head.next,left-1,right-1);
            return head;
        }

        public ListNode reverseN(ListNode head,int n){
            if (n == 1){
                // 记录第 n + 1 个节点
                successor = head.next;
                return head;
            }
            // 以 head.next 为起点，需要反转前 n - 1 个节点
            ListNode last = reverseN(head.next,n-1);
            head.next.next = head;
            //  让反转之后的 head 节点和后⾯的节点连起来
            head.next = successor;
            return last;
        }


    }
}
